1. Field of the Invention
The present invention relates to a method and apparatus for event simulation. More particularly, the present invention uses a bit indexed time queue to speed the execution of simulated events.
2. The Background Art
As electronic systems have become more complex and more sophisticated, due to the high cost and time involved when building circuit prototypes, the desirability for performing simulation of new designs has significantly increased. With the increased complexity of the circuits being simulated, the time involved in performing the simulations has grown to a point where a complex simulation may take more than 24 hours to accomplish. It is vital to perform simulations of electronic circuits as rapidly as possible in order to reduce the total time required to get a product to market.
In order to perform the simulation of an electronic circuit, it is necessary that critical parameters relating to components being used in the circuit be known. Such critical parameters may be operating voltages, internal resistance, power dissipation, and timing characteristics. In addition to other characteristics, timing characteristics of a component determine at what time an event in a simulation will occur. An event, when simulating an electronic circuit, is defined as a change in state of a signal. For example, a rising pulse on one input of an AND gate is an event, as is the step function output of that same AND gate.
In other types of simulation such as flight operations, space simulation, automotive simulation, etc., events may be defined in different ways. It is the handling of events that is the subject of the present invention.
Referring again to the electrical example, the delay time between the two pulses may be one of many timing characteristics of a component involved in a simulation which is used to determine one or more times at which succeeding events should occur. At the time an event is created, often by the simulated occurrence of a previous triggering event, the event is placed in a time queue. As events are operated upon by the simulator, they are typically removed from the queue.
Various methods have been devised for tracking events to be simulated. One method is to place events, in order of occurrence, into an array.
FIG. 1 is a diagram depicting a typical arrangement of simulation events in an array.
Referring to FIG. 1, an array 10 comprises a queue 11 of N events in memory. In order to insert a new event A, it is required that the time at which event A occurs be known. That time is compared against the times associated with other events in the array 10 in order to determine the proper location to place event A into the queue. When that location is determined, events which follow event A's proper location in the queue 11 are bumped one location back in the queue 11, and event A is inserted into the empty location.
For example, if event A in FIG. 1 were to correspond to a simulation time which would place event A between events 5 and 6, such as shown in the figure, event N would be moved to array location N+1. Event N-1 would be moved to the array location previously occupied by event N, and so on, until event 6 was moved into array location 7. Event A would then be inserted into array location 6.
Although storing events in an array is a useful technique for its intended purposes, this method consumes a large quantity of valuable memory space that would be better used for other simulation operations. It would therefore be beneficial to provide a method for storing events into a simulation time queue which would consume low memory.
An alternative method for managing events in a queue uses a doubly linked list.
FIG. 2 is a drawing depicting the layout of a typical doubly linked list 12 used in a simulation time queue.
Referring to FIG. 2, a doubly linked list 12 is shown having N events. Although each record in the queue comprises similar information, only one record will be described, in order to avoid overcomplicating the disclosure. A typical event record 14 has, among other data, a parent link 16, and a child link 18. Parent link 16 points to the event in the simulation time queue which precedes an event in question, and child link 18 points to the event following an event in question. Thus, although the records may not be stored contiguously, they may still be ordered consecutively, based upon the time the particular event records will be processed during the simulation.
FIGS. 3A and 3B are diagrams depicting the method of inserting events into a queue represented by a doubly linked list.
Referring to FIG. 3A, a portion of a simulation time queue 19 is depicted wherein record 7692 has been created by the simulator, and needs to be inserted into the queue 19 in the proper place, in order to have the event associated with record 7692 be simulated at the proper time.
In order to determine that record 7692 should be inserted in the list at a given place in the queue 19 such as between records 3298 and 3299 as seen in FIG. 3A, the simulator may, beginning at the first record, compare the time that record 7692 must be acted upon to the simulation time scheduled for each other record already in the queue, until the proper time slot is found. In a typical simulation queue, there may be thousands of records to search, thus making the process of locating the proper insertion point very time consuming. Therefore, it would be beneficial to provide a method for inserting events into a simulation time queue wherein the proper insertion point is located quickly, without searching every preceding record in the queue.
When the proper insertion point is found, such as seen in FIG. 3A, record 7692 is inserted into the queue 19 in four steps, namely 1) modifying the child pointer 20 of the preceding record to point to record 7692, 2) modifying the parent pointer 22 for the inserted record to reflect the new parent record, 3) modifying the child pointer 24 of the inserted record to reflect the new child record, record 3299 as seen in FIGS. 3B, and 4) modifying the parent pointer 26 for the child record to point to the newly inserted record, as seen with record 3299 in FIG. 3B.
Although the newly inserted record is not necessarily contiguous with its parent record in memory, the parent pointer 16 and the child pointer 18 both provide adequate guidance for the system to locate records in the list in the proper sequence. The main difficulty with this system for managing a simulation time queue is that it is much slower than desired.